package algorithms.tree;

/**
 * 二叉树节点类，包含左节点和右节点
 * 
 * @author shaoyuxia
 *
 * @param <K>
 */
public class BinaryNode<K> extends Node<K> {

	private BinaryNode<K> left;
	private BinaryNode<K> right;
	private BinaryNode<K> parant;
	private K key;
	private int depth;

	public BinaryNode(K key) {
		this.key = key;
	}

	public BinaryNode(K key, BinaryNode<K> left, BinaryNode<K> right) {
		setKey(key);
		this.left = left;
		this.right = right;
	}

	/**
	 * 获取节点（树）的深度
	 * 
	 * 
	 * @return
	 */
	public int getDepth() {
		checkDepth(this, 1);
		return this.depth;
	}

	protected void checkDepth(BinaryNode<K> node, int tmpDepth) {
		if (node != null) {
			if (node.getLeft() == null && node.getRight() == null) {
				if (tmpDepth > depth) {
					depth = tmpDepth;
				}
			} else {
				tmpDepth++;
				checkDepth(node.getLeft(), tmpDepth);
				checkDepth(node.getRight(), tmpDepth);
			}
		}
	}

	/**
	 * 前序遍历，获取key
	 * 
	 * @param node
	 * @param sb
	 */
	public String preorderTraversing() {
		StringBuilder sb = new StringBuilder();
		preorderTraversing(this, sb);
		return sb.toString();
	}

	/**
	 * 后序遍历取key
	 * 
	 * @param node
	 * @param sb
	 */
	public String postorderTraversing() {
		StringBuilder sb = new StringBuilder();
		postorderTraversing(this, sb);
		return sb.toString();
	}

	/**
	 * 中序遍历取key
	 * 
	 * @param node
	 * @param sb
	 */
	public String inorderTraversing() {
		StringBuilder sb = new StringBuilder();
		inorderTraversing(this, sb);
		return sb.toString();
	}

	private void preorderTraversing(BinaryNode<K> node, StringBuilder sb) {
		if (node != null) {
			sb.append(node.getKey()).append(" ");
			if (node.getLeft() != null) {
				preorderTraversing(node.getLeft(), sb);
			}
			if (node.getRight() != null) {
				preorderTraversing(node.getRight(), sb);
			}
		}
	}

	private void postorderTraversing(BinaryNode<K> node, StringBuilder sb) {
		if (node != null) {
			if (node.getLeft() != null) {
				postorderTraversing(node.getLeft(), sb);
			}
			if (node.getRight() != null) {
				postorderTraversing(node.getRight(), sb);
			}
			sb.append(node.getKey()).append(" ");
		}
	}

	private void inorderTraversing(BinaryNode<K> node, StringBuilder sb) {
		if (node != null) {
			if (node.getLeft() != null) {
				inorderTraversing(node.getLeft(), sb);
			}
			sb.append(node.getKey()).append(" ");
			if (node.getRight() != null) {
				inorderTraversing(node.getRight(), sb);
			}
		}
	}

	/*
	 * getter and setters
	 */
	public BinaryNode<K> getLeft() {
		return left;
	}

	public void setLeft(BinaryNode<K> left) {
		this.left = left;
	}

	public BinaryNode<K> getRight() {
		return right;
	}

	public void setRight(BinaryNode<K> right) {
		this.right = right;
	}

	/**
	 * @return the key
	 */
	public K getKey() {
		return key;
	}

	/**
	 * @param key
	 *            the key to set
	 */
	public void setKey(K key) {
		this.key = key;
	}

	/**
	 * @return the parant
	 */
	public BinaryNode<K> getParant() {
		return parant;
	}

	/**
	 * @param parant the parant to set
	 */
	public void setParant(BinaryNode<K> parant) {
		this.parant = parant;
	}
}
